﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Algoritmia.Problems.Puzzles
{
    public class EightPuzzle
    {
        public class State: IEquatable<State>
        {
            private readonly State _previus;
            private readonly string _direction;
            public readonly int Len;
            public readonly Board Board;

            public State(Board b = null, State s = null, string d = null)
            {
                _previus = s;
                _direction = d;
                Board = b;

                if (d == null)
                {
                    Len = 0;
                }
                else
                {
                    Board.Move(d);
                    Len = s.Len + 1;
                }
            }

            private List<string> _Movements()
            {
                if (_previus == null)
                {
                    return new List<string>();
                }
                var seq = _previus._Movements();
                seq.Add(_direction);
                return seq;
            }

            public List<string> Movements()
            {
                var seq = _Movements();
                seq.Reverse();
                return seq;
            }

            public int Hash()
            {
                return Board.Pieces.Aggregate(0, (current, n) => (current << 3) + (n - 1));
            }

            public bool Equals(State other)
            {
                return other != null && Board.Pieces == other.Board.Pieces;
            }
        }

        private readonly Board _board;

        public EightPuzzle(Board board = null)
        {
            _board = board;
        }

        public IEnumerable<State> InitialStates()
        {
            yield return new State(_board);
        }

        public bool IsFinal(State s)
        {
            int k = 1;
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (s.Board.GetItem(i,j) != k)
                    {
                        return false;
                    }
                    k++;
                }
            }
            return true;
        }

        public IEnumerable<string> Decisions(State s)
        {
            return new List<string>{"u","d","l","r"}.Where(dir => s.Board.CanMove(dir));
        }

        public State TakeDecision(State s, String d)
        {
            return new State(null, s, d);
        }

        public bool DestinationIsPromising(State s, String d)
        {
            return true;
        }

        public Tuple<int, int> F(State x)
        {
            return new Tuple<int, int>(x.Len, x.Len);
        }

        public int Opt(int a, int b)
        {
            return Math.Min(a, b);
        }

        public Tuple<int, int> Optimistic(State s)
        {
            return new Tuple<int, int>(s.Len + s.Board.ManhattanDistance(), s.Len);
        }

        public State SuboptimalSolution()
        {
            return null;
        }

        public int Pessimistic(State s)
        {
            return int.MinValue;
        }

        public List<string> Solution(State s)
        {
            return s.Movements();
        }
    }

    public class Board
    {
        public readonly List<int> Pieces;

        public Board(List<int> pieces)
        {
            Pieces = pieces;
        }

        public int GetItem(int i, int j)
        {
            return Pieces[i*3+j];
        }

        private int SetItem(int i, int j, int v)
        {
            Pieces[i*3 + j] = v;
            return v;
        }

        private Tuple<int,int> Freepos()
        {
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (GetItem(i,j) == 9)
                    {
                        return Tuple.Create(i, j);
                    }
                }
            }
            return null;
        }

        public bool CanMove(string dir)
        {
            var hueco = Freepos();
            var i = hueco.Item1;
            var j = hueco.Item2;

            return (dir == "l" && j > 0) || (dir == "r" && j < 2) || (dir == "u" && i > 0) || (dir == "d" && i < 2);
        }

        public void Move(string dir)
        {
            var hueco = Freepos();
            var i = hueco.Item1;
            var j = hueco.Item2;

            if (dir == "l")
            {
                int aux = GetItem(i, j);
                SetItem(i, j, GetItem(i, j - 1));
                SetItem(i, j-1, aux);
            }
            else if (dir == "r")
            {
                int aux = GetItem(i, j);
                SetItem(i, j, GetItem(i, j + 1));
                SetItem(i, j+1, aux);
            }
            else if ( dir == "u")
            {
                int aux = GetItem(i, j);
                SetItem(i, j, GetItem(i-1,j));
                SetItem(i-1, j, aux);
            }
            else if ( dir == "d")
            {
                int aux = GetItem(i, j);
                SetItem(i, j, GetItem(i+1,j));
                SetItem(i+1, j, aux);
            }
        }

        public int ManhattanDistance()
        {
            int dst = 0;
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    int ii = GetItem(i, j)/3;
                    int jj = GetItem(i, j)%3;
                    dst += Math.Abs(i - ii) + Math.Abs(j - jj);
                }
            }
            return dst;
        }
    }
}
